package leetcode.code0918;

public class Solution1 extends Solution918 {

	@Override
	public int maxSubarraySumCircular(int[] nums) {
		int Len = nums.length;
		int[][] dp = new int[Len][4];
		dp[0][0] = nums[0];// 连续最大
		dp[0][1] = nums[0];// 之前最大
		dp[0][2] = nums[0];// 连续最小
		dp[0][3] = nums[0];// 之前最小
		int sum = nums[0];
		for (int i = 1; i < Len; i++) {
			int curNum = nums[i];
			dp[i][0] = Math.max(curNum, dp[i - 1][0] + curNum);// 连续最大
			dp[i][1] = Math.max(dp[i - 1][1], dp[i][0]);
			dp[i][2] = Math.min(curNum, dp[i - 1][2] + curNum);// 连续最小
			dp[i][3] = Math.min(dp[i - 1][3], dp[i][2]);
			sum += curNum;
		}
		return sum == dp[Len - 1][3] ? dp[Len - 1][1] : Math.max(dp[Len - 1][1], sum - dp[Len - 1][3]);
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
	}

}
